import java.util.*;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {
    }

    TreeNode(int val) {
        this.val = val;
    }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}
public class Main {

/*
 *  给你二叉树的根节点 root ，返回其节点值的层序遍历 。 （即逐层地，从左到右访问所有节点）。
* */

    /*在levelOrder函数中，我们首先创建一个结果列表result来存储层序遍历的结果。
    然后，我们创建一个队列queue并将根节点入队。
    接下来，我们使用一个循环来处理每一层的节点。
    在循环中，我们首先获取当前层的节点数levelSize，然后创建一个列表levelValues来存储当前层的节点值。
    接着，我们从队列queue中取出levelSize个节点，将它们的值加入levelValues列表，并将它们的非空子节点加入队列。完
    当前层的处理后，我们将levelValues列表加入result列表。最终，当队列为空时，我们完成了二叉树的层序遍历。

    * */

public List<List<Integer>> levelOrder(TreeNode root){
    List<List<Integer>> result=new ArrayList<>();
    if(root==null){
        return result;
    }
    Queue<TreeNode> queue=new LinkedList<>();
    queue.offer(root);
    while (!queue.isEmpty()){
        int levelSize = queue.size();
        List<Integer> levelValues = new ArrayList<>();
        for (int i =0;i<levelSize;i++){
            TreeNode node=queue.poll();
            levelValues.add(node.val);
            if(node.left!=null){
                queue.offer(node.left);
            }
            if(node.right!=null){
                queue.offer(node.right);
            }
        }
        result.add(levelValues);

    }
    return result;
}
/*
* 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，
* 最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
* */

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q){
        if(root==null||p==null||q==null){
            return null;
        }
        if(p==root||q==root){
            return root;
        }
        if (isSubtree(root.left, p) && isSubtree(root.left, q)) {
            return lowestCommonAncestor(root.left, p, q);
        }
        if (isSubtree(root.right, p) && isSubtree(root.right, q)) {
            return lowestCommonAncestor(root.right, p, q);
        }
        return root;
 /*       if(isSubtree(p,q)){
            return  p;
        }else if(isSubtree(q,p)){
            return q;
        }
        int height1=getHeight(root)-getHeight(p);
        int height2=getHeight(root)-getHeight(q);
        Stack<TreeNode> stack=new Stack<>();
        while(height1>0&&height2>0){

            if(isSubtree(root.left,p)&&isSubtree(root.left,q)){
                stack.push(root.left);
            }
            if(isSubtree(root.right,p)&&isSubtree(root.right,q)){
                stack.push(root.right);
            }
            height1--;
            height2--;
        }
        if(!stack.empty())  return stack.pop();
        else return root;*/

    }
    public int getHeight(TreeNode root) {
        if (root == null) {
            return 0;
        } else {
            int leftHeight = getHeight(root.left);
            int rightHeight = getHeight(root.right);
            return Math.max(leftHeight, rightHeight) + 1;
        }
    }
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        if (root == null) {
            return false;
        }
        if (isSameTree(root, subRoot)) {
            return true;
        }
        return isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot);
    }

    private boolean isSameTree(TreeNode p, TreeNode q) {
        if (p == null && q == null) {
            return true;
        }
        if (p == null || q == null) {
            return false;
        }
        if (p.val != q.val) {
            return false;
        }
        return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
    }

    public TreeNode lowestCommonAncestor2(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || root == p || root == q) {
            return root;
        }

        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);

        if (left != null && right != null) {
            return root;
        } else if (left != null) {
            return left;
        } else {
            return right;
        }
    }


    /*
    * public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {

    if (isSubtree(root.left, p) && isSubtree(root.left, q)) {
        return lowestCommonAncestor(root.left, p, q);
    }
    if (isSubtree(root.right, p) && isSubtree(root.right, q)) {
        return lowestCommonAncestor(root.right, p, q);
    }
    return root;
}

public int getHeight(TreeNode root) {
    return getHeightHelper(root, 0);
}

private int getHeightHelper(TreeNode root, int height) {
    if (root == null) {
        return height;
    }
    int leftHeight = getHeightHelper(root.left, height + 1);
    int rightHeight = getHeightHelper(root.right, height + 1);
    return Math.max(leftHeight, rightHeight);
}

public boolean isSubtree(TreeNode root, TreeNode subRoot) {
    if (root == null) {
        return false;
    }
    if (isSameTree(root, subRoot)) {
        return true;
    }
    return isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot);
}

private boolean isSameTree(TreeNode p, TreeNode q) {
    if (p == null && q == null) {
        return true;
    }
    if (p == null || q == null) {
        return false;
    }
    if (!p.val.equals(q.val)) {
        return false;
    }
    return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
}
    * */

    /*给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历，
     inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。*/
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return buildTreeHelper(preorder, inorder, 0, 0, inorder.length - 1);
    }

    private TreeNode buildTreeHelper(int[] preorder, int[] inorder, int preStart, int inStart, int inEnd) {
        if (preStart > preorder.length - 1 || inStart > inEnd) {
            return null;
        }

        TreeNode root = new TreeNode(preorder[preStart]);

        int inIndex = 0;
        for (int i = inStart; i <= inEnd; i++) {
            if (inorder[i] == root.val) {
                inIndex = i;
                break;
            }
        }
        root.left=buildTreeHelper(preorder,inorder,preStart+1,inStart,inIndex-1);
        root.right=buildTreeHelper(preorder,inorder, preStart + inIndex - inStart + 1,inIndex+1,inEnd);
        return root;
    }

    public static void main(String[] args) {
        System.out.println("Hello world!");
    }
}